package main

import (
	"fmt"
	"strconv"
)

func cellsInRange(s string) []string {
	var result []string
	for i := s[0]; i <= s[3]; i++ {
		length, _ := strconv.ParseInt(s[4:5], 10, 64)
		for j, _ := strconv.ParseInt(s[1:2], 10, 64); j <= length; j++ {
			result = append(result, (string(i) + strconv.Itoa(int(j))))
		}
	}
	return result
}

func numberOfMatches(n int) int {
	temp := n
	result := 0
	for temp > 1 {
		offset := temp & 1
		temp /= 2
		result += temp
		temp += offset
	}
	return result
}

func maximumWealth(accounts [][]int) (ans int) {
	for _, account := range accounts {
		sum := 0
		for _, val := range account {
			sum += val
		}
		if sum > ans {
			ans = sum
		}
	}
	return
}

func fib(n int) int {
	if n < 2 {
		return n
	}
	p := 0
	q := 0
	r := 1
	for i := 2; i < n+1; i++ {
		p = q
		q = r
		r = (p + q) % 1000000007
	}
	return r
}

func main() {
	//fmt.Println(cellsInRange("K1:L2"))
	//fmt.Println(cellsInRange("A1:F1"))

	//fmt.Println(numberOfMatches(7))
	//fmt.Println(numberOfMatches(14))

	//fmt.Println(maximumWealth([][]int{{1, 2, 3}, {3, 2, 1}}))
	//fmt.Println(maximumWealth([][]int{{1, 5}, {7, 3}, {3, 5}}))
	//fmt.Println(maximumWealth([][]int{{2, 8, 7}, {7, 1, 3}, {1, 9, 5}}))

	fmt.Println(fib(2))
	fmt.Println(fib(3))
	fmt.Println(fib(4))
	fmt.Println(fib(45))
}
